﻿'''
题目描述
给定两个字符串s1和s2和正整数K，其中s1长度为n1，s2长度为n2，在s2中选一个子串，满足:
该子串长度为n1+k
该子串中包含s1中全部字母，
该子串每个字母出现次数不小于s1中对应的字母，
我们称s2以长度k冗余覆盖s1，给定s1，s2，k，求最左侧的s2以长度k冗余覆盖s1的子串的首个元素的下标，如果没有返回**-1**。
输入描述
输入三行，第一行为s1，第二行为s2，第三行为k，s1和s2只包含小写字母
备注
0 ≤ len(s1) ≤ 1000000
0 ≤ len(s2) ≤ 20000000
0 ≤ k ≤ 1000
输出描述
最左侧的s2以长度k冗余覆盖s1的子串首个元素下标，如果没有返回**-1。**
示例1
输入
ab
aabcd
1
输出
0
说明
子串aab和abc符合要求，由于aab在abc的左侧，因此输出aab的下标：0
示例2
输入
abc
dfs
10
输出
-1
说明
s2无法覆盖s1，输出 -1
解题思路
这个题目要求在字符串 s2 中找到一个满足特定条件的子串，然后返回这个子串的首个元素的下标。如果没有找到符合条件的子串，
则返回 -1。
考察的是字符串处理和滑动窗口等算法技巧。你需要在遍历 s2 的过程中检查每一个可能的子串，并判断它是否符合题目要求。
题目的要求如下：
给定两个字符串 s1 和 s2 以及一个正整数 k，其中 s1 的长度为 n1，s2 的长度为 n2。
在 s2 中找到一个子串，这个子串的长度为 n1 + k。
这个子串必须包含 s1 中的所有字母，并且每个字母在子串中出现的次数不能少于在 s1 中出现的次数。
你需要找到第一个满足上述条件的子串在 s2 中的起始位置下标。如果没有符合条件的子串，返回 -1。
示例说明：
s1 = "ab"，s2 = "aabcd"，k = 1：在s2中，长度为 n1 + k = 3 的子串有 “aab” 和 “abc”。这两个子串都包含s1的所有字母，
并且每个字母出现的次数都不小于 s1 中的次数。因为 “aab” 出现在 “abc” 的左侧，所以返回 “aab” 的起始位置 0。
s1 = "abc"，s2 = "dfs"，k = 10：s2 中没有任何长度为 n1 + k = 13 的子串包含 s1 中的所有字母，因此返回 -1。
'''
#输入描述
#输入三行，第一行为s1，第二行为s2，第三行为k，s1和s2只包含小写字母
#输出描述
#最左侧的s2以长度k冗余覆盖s1的子串首个元素下标，如果没有返回**-1。**

import re   #使用正则表达式
#读取输入
s1 = input()
s2 = input()
k = int(input())

if len(s1) + k > len(s2):
    print("-1")
    exit()

#对s1去重并按字典排序
sorted_s1 = list(sorted(set(s1)))
#统计s1中各个字符个数
char_s1_list = {}
for c in sorted_s1:
    pattern = c + '+'
    count = 0
    for match in re.finditer(pattern,s1):
        count += len(match.group())
    char_s1_list[c] = count  #要比较value，需使用字典
#遍历s2，查找满足条件的下标
output_index = -1
for i in range(len(s2) - len(s1) - k + 1):
    #要比较的字符串
    cmp_str = s2[i:i + len(s1) + k]
    #遍历s1的字符和个数，并和窗口的比较
    valid = True
    for c in sorted_s1:
        pattern = c + '+'
        count = 0
        for match in re.finditer(pattern,cmp_str):  
            #不匹配会返回空迭代器，len(match.group())是否可用？，如不可用，可考虑转换为list()判断其长度
            #实际测试len(match.group())为空也可用
            count += len(match.group())
        if count < char_s1_list[c]:
            valid = False   #数量不满足，跳出循环
            break
    if valid:
        output_index = i
        break
#输出结果
print(output_index)

